lib/Mi manual de algoritmos/version_maraton_interuniversitaria_2008-2/src/geometria/is_convex_polygon.cpp

   1 /*
   2   Returns positive if a-b-c make a left turn.
   3   Returns negative if a-b-c make a right turn.
   4   Returns 0.0 if a-b-c are colineal.
   5  */
   6 double turn(const point &a, const point &b, const point &c){
   7   double z = (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
   8   if (fabs(z) < 1e-9) return 0.0;
   9   return z;
  10 }
  11
  12 /*
  13   Returns true if polygon p is convex.
  14   False if it's concave or it can't be determined
  15   (For example, if all points are colineal we can't
  16   make a choice).
  17  */
  18 bool isConvexPolygon(const vector<point> &p){
  19   int mask = 0;
  20   int n = p.size();
  21   for (int i=0; i<n; ++i){
  22     int j=(i+1)%n;
  23     int k=(i+2)%n;
  24     double z = turn(p[i], p[j], p[k]);
  25     if (z < 0.0){
  26       mask |= 1;
  27     }else if (z > 0.0){
  28       mask |= 2;
  29     }
  30     if (mask == 3) return false;
  31   }
  32   return mask != 0;
  33 }